package code1.stack_and_queue;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 原题链接：https://leetcode.cn/problems/top-k-frequent-elements/
 */
public class P347 {

    //优先级队列：保证每次取出来的元素都是队列中的最小或最大的元素,是一个披着队列外衣的堆，底层原理是完全二叉树
    //因为这种特性，凡事说，求第K个，或者前K个的问题，基本上就可以用优先级队列，也就是堆这种数据结构来搞定
    //大顶堆：父节点大于等于左右孩子，采用大顶堆实现的优先级队列队头元素最大
    //小顶堆：父节点小于等于左右孩子，采用小顶堆实现的优先级队列队头元素最小

    //返回前k个高频元素
    public static int[] topKFrequent(int[] nums, int k) {
        //用map统计各数字出现频率
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(map.get(nums[i])==null){
                map.put(nums[i],1);
            }else{
                map.put(nums[i],map.get(nums[i])+1);
            }
        }
        //创建优先级队列(大顶堆),即出现次数最高的在队头
        PriorityQueue<int[]> pq=new PriorityQueue<>((pair1,pair2)->pair2[1]-pair1[1]);      //pair[0]为元素值，pair[1]为出现频率
        //遍历map，将元素添加进优先级队列
        Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
        for(Map.Entry<Integer, Integer> entry: entrySet){
            pq.add(new int[]{entry.getKey(),entry.getValue()});
        }
        //依次取出前k个最大的
        int[] res=new int[k];
        for(int i=0;i<k;i++){
            res[i]=pq.poll()[0];
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums={1,1,1,2,2,3};
        int[] ans = topKFrequent(nums, 2);
        for(int i=0;i<ans.length;i++){
            System.out.println(ans[i]);
        }
    }

}
